package com.LatitudeYao;
import java.util.*;

/**
 * Created by GTS on 2017/8/22.
 */
public class ManySortByYM {
    public static int findMiddle(int[] array, int low ,int high){//查询中州元素所在位置
        int temp = array[low];//默认首元素最小
        while (low < high){//外层执行全部循环
            while (low < high && array[high] < temp){//定位到第一个比temp小的元素。如果array[high] 》 temp,不管，直接左移游标
                high --;
            }
            array[low] = array[high];//移动到枢轴左侧
            while (low < high && array[low] > temp){//定位到第一个比temp大的元素
                low++;
            }
            array[high] = array[low];//此元素移动到右侧
        }
        array[low] = temp;//回写用作缓存的那个元素
        return low;//返回游标
    }
    public static int[] quickSort(int[] array,int low,int high){
        if(low < high){
            int middle = findMiddle(array,low,high);
            quickSort(array,0,middle-1);
            quickSort(array,middle+1,high);
        }
        return array;
    }
    //选择排序
    public static int[] selectSort(int[] array){
        int temp = 0;
        for (int i = 0; i <array.length ; i++) {
            int k = i;//保存当前下标
            for (int j = array.length-1; j > i ; j--) {
                if(array[j] < array[i]){//找到最小的那个值所在的下标k
                    k=j;//确定最小的下标
                }
            }
            temp = array[i];//交换
            array[i] = array[k];
            array[k] = temp;
        }
        return array;
    }
    //插入排序
    public static int[] insertSort(int[] array){
        int temp = 0;
        int j = 0;//确定下标
        for (int i = 0; i < array.length ; i++) {
            temp = array[i];//先把array[i]保存起来
            for ( j = i; j > 0 && temp < array[j-1]; j--) {
                array[j] = array[j-1];//已排序的部分后移，空出待插入位置
            }
            array[j] = temp;//执行插入，回写到空出来的位置
        }
        return array;
    }
    public static int [] bubbleSort(int[] array){

        return array;
    }
    public static void main(String[] args) {
        int [] arr = {1,3,2,4,6,8,7,9,10};
        System.out.println("Before InsertSort");
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println("After InsertSort");
        System.out.println(Arrays.toString(arr));


        int [] arr2 = {1,3,2,4,6,8,7,9,10};
        System.out.println("Before SelectSort");
        System.out.println(Arrays.toString(arr2));
        selectSort(arr2);
        System.out.println("After SelectSort");
        System.out.println(Arrays.toString(arr2));


        int [] arr3 = {1,3,2,4,6,8,7,9,10};
        System.out.println("Before QuickSort");
        System.out.println(Arrays.toString(arr3));
        selectSort(arr3);
        System.out.println("After QuickSort");
        System.out.println(Arrays.toString(arr3));


    }
}
